Die Hard 3 and The Jar Filling Problem - Through the Lens of Diophantine Equations

Posted on Sat Oct 31 2020. 7 min Read.

Mathematics Hackerrank

Bruce Willis in die hard 3 - illustration

Using two jars of capacities 5 gallons and 3 gallons, measure out 4 gallons exactly.
-- Die Hard (basically)

I could list out the whole script of the movie in this instance, which most of the websites listed on the first page of google will do, so I am not going to do that here. Instead of giving you a solution to the immediate problem, i.e. producing 4 gallons of water using jars of sizes 5 gallons and 3 gallons, I will instead take you through a journey that will teach you to determine why, how and when this is possible. In short, we're going to learn how to fish today.

Solving the puzzle. #

Let's see. We have jars, of capacities 5 gallons and 3 gallons respectively. We need to measure out exactly 4 gallons of water. We can pour water in and out of the jars and between them, but we have no way of measuring nor leveling the amount of water in the two jars against each other. How would one do it?

If you are like most people (and me), you will get stuck like this:

Step 1: Pour water into the 5 gallon jar
Step 2: Pour 3 gallons from the 5 gallon jar into the 3 gallon jar.
Step 3: Empty the 3 gallon jar. Now you have 2 gallons of water in the 5 gallon jar.

Wait what? We wanted 4 gallons of water, not 2. Now don't go about saying that you can repeat this process to get 4 gallons of water. Bruce Willis did not have that privilege and neither do you. Fret not, let's begin thinking in the opposite direction. This way we'll reach the solution this time.

Step 1: Pour water into the 3 gallon jar
Step 2: Empty out the 3 gallon jar into the 5 gallon jar.
Step 3: Re-fill the 3 gallon jar. Empty it into the 5 gallon jar until the 5 gallon jar becomes full.

If you are with me until this point, we now have 1 gallon of water in the 3 gallon jar, and the 5 gallon jar is full
Step 4: Empty out the 5 gallon jar, and pour the 1 gallon water from the 3 gallon jar into the 5 gallon jar. Now fill the 3 gallon jar and again empty it into the 5 gallon jar.
Step 5: Now the 5 gallon jar contains 4 gallons of water.

If you had come here for a quick fix, to find a solution to this problem, then you may leave now. There's some maths ahead, as we will try to explore how we can determine the feasibility of the die-hard-ness of any two water jars. Let's begin!

Formulating the Word Problem in terms of Mathematics: #

I'm going to formulate this problem in teerms of maths in a quite unconventional way. But bear with me. Let's start by taking the final amount of water that we need.

$4$

This can be decomposed.

$= 1 + 3$

We have 3 already, but we need a 1 now.

$ = 3 - 2 + 3 $

Hmm, this is getting interesting. Now, I can replace the 2 with the difference between the original jar volumes.

$ = 3 - (5 - 3) + 3$

$ = 3 \times 3 - 5 $

There are a couple of reasons that I am expressing the problem in this way. We can notice a couple of things through this solution:

We obtained all values of volumes, right from 1 upto 5 gallons using this method. As we can obtain 2 gallons and 3 gallons, we can go all the way up to 8 gallons, i.e. the obtainable values of the volumes of water range from 1 to 8 gallons.
The final equation shows 3x3 and -1x5. If you look at the solution closely, the jar with volume 3 has been filled exactly 3 times and the jar with volume 5 has been emptied exactly once! This is not a coincidence. In fact, each volume that is obtainable from the two jars is a linear combination of their respective volumes, like 2 can be obtained as (5 - 3) and 1 can be obtained as (3 - (5 - 3)).

Let us consider a and b denote the volumes of the first and second jars respectively. For obtaining any volume c from the two jars, the volume c must be a linear combination of the capacity-volumes of the two jars, i.e.

$$ a \times x + b \times y = c$$

Where x and y are two integers. If x and y are not integers, then we won't be able to measure out the volume c accurately. Also, c should be a positive integer ( What is negative volume anyways? )

Star of the Show: Linear Diophantine Equations: #

I am no professor, but I will give you a linear equation and you are going to tell me the solution.

$$ x + y = 2 $$

That's it.

One might rant, "Oh but Sandesh! Don't you know that you need as many equations as variables to solve a system of linear equations?" Ah yes. But we are not talking about a system of linear equations. We are just talking about an equation.

"The solution is simple then!", one might exclaim. One of the solutions is $x = 1$ and $y = 1$. Another one can be $x = 3$ and $y = -1$. In fact, plotting the equation gives us a straight line, all points on which, satisfy the given equation and are its solutions.

We are particularly interested in Integer solutions of a given linear equation.

That's where the Linear Diophantine Equation comes into play!

The simplest linear Diophantine equation takes the form ax + by = c, where a, b and c are given integers.

- Wikipedia

For a diophantine equation to be solvable, the HCF (or GCD) of the coefficients, $a$ and $b$ should evenly divide (divide without a remainder) the constant term $c$. This can be seen from the properties of a integer.

Say, $h$ be the GCD of $x$ and $y$, so it divides $x$ and $y$ evenly. Then $h$ divides every multiple of $y$ evenly also and every multiple of $x$ too. That means $ax$ and $by$ are divisible by $h$ and so their sum $ax + by$ is also evenly divisible by $h$. For the equation $c$ should also be evenly divisble by $h$ as $ax + by$ gives us a integer, and being RHS, $c$ should be evenly divisble by $h$ as well for us to get an integer.

In order to check if it is possible to obtain $v$ volume with jars of capacities $a$ and $b$, it's very simple.

import math

def check_possibility(a, b, v):
  return v % math.gcd(a, b) == 0 and v <= (a+b)

Sticking around for more: Finding out Number of times to fill and Empty a Jar. #

With this much of knowledge, you will be able to solve a hackerrank problem relating the same. The question asks if it is indeed possible to measure out exactly 'v' volume given jars of volumes 'a' and 'b'. But if you want to know the exact number of times the jars need to be filled and emptied, then feel free to stick around.

Moving forward, I expect you already know about Euclid's algorithm to find out the GCD between two numbers. If not, then brace yourselves, a post is coming soon! In the meantime, feel free to check out wikipedia for the algorithm.

We are going to reverse the Algorithm for our own purposes. I will demonstrate with an example here so that it will be clearer. Let's start with an equation

$$ 5x + 3y = 4 $$

The GCD of $5$ and $3$ is $1$, which we need to show as the linear combination of the two. Let's start by first deriving the GCD using Euclid's algorithm:
$$ 5 = 3 \times 1 + 2 \ ... (1)$$
$$ 3 = 2 \times 1 + 1 \ ... (2)$$
$$ 2 = 1 \times 2 + 0 \ ... (3) $$

With these, the algorithm terminates, and the last remaining quotient, i.e. 1 is the GCD. Let's reverse this method to find the linear combination. Let's start by writing the remainders on the LHS of the equations

$$
2 = 5 - 3\times1 \ ... (4)
$$ $$
1 = 3 - 2\times 1\ ... (5)
$$ $$
0 = 2 - 1 \times 2\ ... (6)
$$
Now let's express our GCD in terms of our initial values, $5$ and $3$
$$
1 = 3 - (5-3) \times 1 \ ... (using \ 5, \ 4)
$$ $$
1 = 3\times 2 - 5
$$
Simple as that! Now to express our constant, i.e. $4$ in terms of $5$ and $3$, we can do a simple multiplication, i.e. $1\times4$. So our final equation values become
$$
5x + 3y = 4
$$ $$
\implies 5 x + 3y = 4 \times 1
$$ $$
\implies 5x + 3y = 4 \times (3\times 2 - 5)
$$$$
\implies 5x + 3y = -4\times 5 +3\times 8
$$
Indeed, the maths checks out. Using these values of coefficients, it is possible to derive every combination of volume from $min(a, b)$ to $sum(a, b)$.

Indeed, it is really easy to solve simple equations like these with hand, but in order to obtain results for large values of $a$ and $b$ we need a computer.

Let's begin with our original equation:

$$ ax + by = c $$

Using long form division and assuming $ a> b$, one can safely say that

$$ a = b \times q + r $$

Assuming $q$ as the quotient and $r$ as the remainder.

$$ ( b \times q + r) x + by = c $$

$$ \implies bqx + rx + by = c $$

$$ \implies b(qx + y) + rx = c $$

Now in this equation, we have smaller coefficients. Let's substitute the values for unknowns with symbols as:

$$ v = x \ and \ u = (qx + y) $$

$$ also,\ u = (qv + y)\ [Using \ preceding \ equation] $$

So finally, the equation has reduced to
$$
bu + rv = c
$$
Which is equivalent to our original equation but has smaller coefficients. Also, the value of $r$ keeps on converging until it reaches $0$. That will be our base case as we will try to solve this problem using recursion.

Let's Code it up! #

Phew! We have finally arrived at the final part of this tutorial. Let's write a simple program to find out the coefficients, i.e. number of times to empty and fill the jars. Please keep in mind that this program solves the original equation, i.e. $ ax + by = c$.


def getCoefficients(a, b, c):
	# a, b are the volumes of the jars and c is the target volume
  quotient, remainder = divmod(a, b)
  if remainder == 0:
    return [0, c/b]
  solvable = getCoefficients(b, r, c)
  v = solvable[1]
  u = solvable[0]
  return [v, u - quotient * v ]

Running the program for inputs 5, 3, 4 yields output -4, 8 which are the values required. Substituting in original equation:

$$ 5x + 3y = 4$$

$$ 5 \times -4 + 3 \times 8 = 4 $$

Reducing $4$ from both sides,

$$ 5 \times -1 + 3 \times 2 = 1 $$

Hence, the we need to empty the 5 gallon jar 1 time and 3 gallon jar 2 times!

That's about it! If you want to read more blog posts like this, then please connect with subscription to the newsletter on the homepage.

Thank you!

References: #

← Previous Post:

Leonardo's Prime Numbers: Hackerrank Solution

Next Post: →

Ownership of Obscure Songs and Lurking in comments